package LC;

/**
 * @author lhn
 * @date 2024-09-22 19:17
 * 134. 加油站
 * 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
 * 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
 *
 */

public class GasStation {
    public static void main(String[] args) {
        int[] gas1 = {1, 2, 3, 4, 5};
        int[] cost1 = {3, 4, 5, 1, 2};
        System.out.println(canCompleteCircuit(gas1, cost1));    // 3

//        int[] gas2 = {2, 3, 4};
//        int[] cost2 = {3, 4, 3};
//        System.out.println(canCompleteCircuit(gas2, cost2));    // -1
//
//        int[] gas3 = {5, 1, 2, 3, 4};
//        int[] cost3 = {4, 4, 1, 5, 1};
//        System.out.println(canCompleteCircuit(gas3, cost3));    // 4
//
//        int[] gas4 = {3, 3, 4};
//        int[] cost4 = {3, 4, 4};
//        System.out.println(canCompleteCircuit(gas4, cost4));    // -1
//
//        int[] gas5 = {5, 8, 2, 8};
//        int[] cost5 = {6, 5, 6, 6};
//        System.out.println(canCompleteCircuit(gas5, cost5));    // 3
//
//        int[] gas6 = {5, 5, 1, 3, 4};
//        int[] cost6 = {8, 1, 7, 1, 1};
//        System.out.println(canCompleteCircuit(gas6, cost6));    // 3
    }

    // 找到亏损最大的点，如果剩余油量小于0，则返回-1，否则返回最小剩余油量所在的加油站的下标，等待其他加油站补充油
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int spare = 0;  // 剩余油量
        int minSpare = Integer.MAX_VALUE;   // 剩余油量最小值
        int minIndex = 0;
        for (int i = 0; i < n; i++) {
            spare = spare + gas[i] - cost[i];
            if (spare < minSpare) {
                minSpare = spare;
                minIndex = i;
            }
        }

        return spare < 0 ? -1 : (minIndex + 1) % n;
    }
}
